package graph;

import list.Stack;

/**
 * description:
 * author:张腾
 * date:2021-04-13
 */

/**
 * 使用深度优先搜索给顶点排序
 * 栈的思想
 */
public class DepthFirstOrder {

    //索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean[] marked;
    //使用栈存储顶点序列
    private Stack<Integer> reversePost;

    public DepthFirstOrder(DiGraph G){
        this.marked = new boolean[G.V()];
        this.reversePost = new Stack<Integer>();
        for (int i = 0; i < G.V(); i++) {
            if (!marked[i]){
                dfs(G,i);
            }
        }
    }

    //基于深度优先搜索，检测图G中是否有环
    private void dfs(DiGraph G,int v){
        marked[v] = true;
        for (Integer w : G.adj(v)) {
            if (!marked[w]){
                dfs(G,w);
            }
        }
        reversePost.push(v);
    }

    //获取顶点线性序列
    public Stack<Integer> reversePost(){

        return reversePost;
    }
}
